spatial scan statist approxim perform studi deepak agarw andrew mcgregor jeff phillip suresh venkatasubramanian zhengyuan zhu spatial scan statist determin hotspot spatial data wide epidemiolog biosurveil recent year effort invest design effici algorithm find high discrep region method rang fast heurist special case gener grid base method effici approxim algorithm provabl guarante perform qualiti paper make number contribut comput studi spatial scan statist describ simpl exact algorithm find largest discrep region domain propos approxim algorithm larg class discrep function includ kulldorff scan statist improv approxim versu run time trade prior method extend simpl exact approxim algorithm data set lie natur grid accumul grid fourth conduct detail experiment comparison method number method demonstr approxim algorithm superior perform practic prior method exhibit good perform accuraci trade extant method includ paper suitabl data set modestli size data set order million data point method scale massiv data set natur examin small space stream algorithm yield accur answer provid neg result show stream algorithm provid approxim optim answer discrep maxim problem space linear input 